package com.dy.分类.递归回溯分治.生成括号.生成合理括号;

import java.util.LinkedList;
import java.util.List;

/**
 * 22
 * 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
 * <p>
 * 例如，给出 n = 3，生成结果为：
 * <p>
 * [
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 */

/**
 * 思路：
 * 合理：1、左括号和右括号都不能大于n
 * 2、右括号不能先于左括号生成，即当右括号的数量大于左括号时，停止，return
 */
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new LinkedList<>();
        generate("", n, n, res);
        return res;
    }

    void generate(String item, int left, int right, List<String> res) {
        //当剩下的括号左括号比右括号多，说明item里用掉的右括号比左括号多
        if (left < 0 || right < 0 || left > right) return;
        else if (left == 0 && right == 0) {
            res.add(item);
            return;
        } else {
            generate(item + "(", left - 1, right, res);
            generate(item + ")", left, right - 1, res);
        }
    }

    void generate2(String item, int left, int right, List<String> res) {

        if (left == 0 && right == 0) {
            res.add(item);
            return;
        }
        //当左括号大于0，先放左括号
        if (left > 0) {
            generate(item + "(", left - 1, right, res);
        }
        //当剩下的左括号小于右括号，放右括号
        if (left < right) {
            generate(item + ")", left, right - 1, res);
        }
    }



    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.generateParenthesis(3);
    }
}
